package 动态规划专项训练.动态规划训练1;

/** 322.零钱兑换
 * 求值型动态规划
 * @author zx
 * @create 2022-03-29 20:42
 */
public class Num322 {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        int n = coins.length;
        //初始化条件
        f[0]= 0;
        for(int i = 1;i <= amount;i++){
            f[i] = Integer.MAX_VALUE;//设置为amount不可达
            //最后一个硬币A[j]
            for(int j = 0;j < n;j++){
//                //i >= coins[j]：防止负数的出现(如果要拼3块钱,就不可能出现5块钱的硬币)
//                //拼不出要的那种方案
//                if(i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE){
//                    //状态转移方程
//                    f[i] = Math.min(f[i - coins[j]] + 1,f[i]);
//                }
                if(i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE && f[i - coins[j]] + 1 < f[i]){
                    f[i] = f[i - coins[j]] + 1;
                }
            }
        }
        if(f[amount] == Integer.MAX_VALUE){
            f[amount] = -1;
        }
        return f[amount];
    }
}